package com.algorithm.lesson_05;

import java.util.Stack;

/**
 * 汉诺塔问题（现在限制不能从最左侧的塔直接移动到最右 侧， 也不能从最右侧直接移动到最左侧， 而是必须经过中间）
 * 
 * @author Administrator
 *
 */
public class Hanoi {
	// F(N,from,to) 将1-N号砖块从from移动到to
	// 1:F(N-1,L,R) 将1~N-1从左边移动到右边
	// 2:N->M 将第N个从左边移动到中间
	// 3:F(N-1,R,L) 将1~N-1从右边移动到左边
	// 4:N->R 将第N个从中间移动到右边
	// 5:F(N-1,L,R) 将1~N-1从左边移动到右边

	/**
	 * 汉诺塔递归方法
	 * 
	 * @param n
	 *            砖块个数
	 * @param left
	 *            左盘标记，仅用于输出
	 * @param mid
	 *            中盘标记，仅用于输出
	 * @param right
	 *            右盘标记，仅用于输出
	 * @return
	 */
	public static int HanoiRecursive(int n, String left, String mid, String right) {
		if (n < 1) {
			return 0;
		}

		return process(n, left, mid, right, left, right);
	}

	/**
	 * 将n个砖块从from位置移动到to位置的解法
	 * 
	 * @param n
	 * @param left
	 * @param mid
	 * @param right
	 * @param from
	 * @param to
	 * @return
	 */
	public static int process(int n, String left, String mid, String right, String from, String to) {
		if (n == 1) {
			if (from.equals("mid") || to.equals("mid")) {
				// from和to中有一个为mid from->to
				System.out.println("Move 1 from " + from + " to " + to);
				return 1;
			} else {
				// 1:from->mid
				System.out.println("Move 1 from " + from + " to " + mid);
				// 2:mid->to
				System.out.println("Move 1 from " + mid + " to " + to);
				return 2;
			}
		} else {
			if (from.equals("mid") || to.equals("mid")) {
				// from或to有一个为mid，并求出另外一个位置记为another
				String another = (from.equals(left) || to.equals(left)) ? right : left;
				// 将1~N-1从from移动到another
				int part1 = process(n - 1, left, mid, right, from, another);
				// 将第N个从from移动到to
				int part2 = 1;
				System.out.println("Move " + n + " from " + from + " to " + to);
				// 将1~N-1从another移动到to
				int part3 = process(n - 1, left, mid, right, another, to);
				return part1 + part2 + part3;
			} else {
				// from或to都不是中间
				// 将1~N-1从from移动到to
				int part1 = process(n - 1, left, mid, right, from, to);
				// 将N从from移动到mid
				int part2 = 1;
				System.out.println("Move " + n + " from " + from + " to " + mid);
				// 将1~N-1从to移动到from
				int part3 = process(n - 1, left, mid, right, to, from);
				// 将N从mid移动到to
				int part4 = 1;
				System.out.println("Move " + n + " from " + mid + " to " + to);
				// 将1~N-1从from移动到to
				int part5 = process(n - 1, left, mid, right, from, to);
				return part1 + part2 + part3 + part4 + part5;
			}
		}
	}

	public static enum Action {
		No, // 无操作
		LToM, // 左塔移动到中塔
		MToL, // 中塔移动到左塔
		RToM, // 右塔移动到中塔
		MToR// 中塔移动到有塔
	}

	/**
	 * 堆栈实现汉诺塔
	 * 
	 * @return
	 */
	public static int hanoiStack(int n, String left, String mid, String right) {
		// 用栈来模拟汉诺塔的三个塔
		Stack<Integer> leftStack = new Stack<>();
		Stack<Integer> midStack = new Stack<>();
		Stack<Integer> rightStack = new Stack<>();

		// 将三个塔的栈分别压入最大值，用以判断将要压入的元素是否比当前栈顶的元素更小
		leftStack.push(Integer.MAX_VALUE);
		midStack.push(Integer.MAX_VALUE);
		rightStack.push(Integer.MAX_VALUE);

		// 将n个砖块全部压入左塔栈中
		for (int i = n; i > 0; i--) {
			leftStack.push(i);
		}

		Action[] record = { Action.No };

		int step = 0;
		while (rightStack.size() != n + 1) {
			// 依次检测4种动作
			step += fStackTotStack(record, Action.LToM, Action.MToL, midStack, leftStack, mid, left);
			step += fStackTotStack(record, Action.MToL, Action.LToM, leftStack, midStack, left, mid);
			step += fStackTotStack(record, Action.MToR, Action.RToM, rightStack, midStack, right, mid);
			step += fStackTotStack(record, Action.RToM, Action.MToR, midStack, rightStack, mid, right);
		}

		return step;
	}

	/**
	 * 将f栈的栈顶移动到t栈中
	 * 
	 * @param record
	 *            记录上一步的动作
	 * @param preAction
	 *            当前动作的相反动作
	 * @param nowAction
	 *            当前的动作
	 * @param fStack
	 * @param tStack
	 * @param from
	 * @param to
	 * @return
	 */
	public static int fStackTotStack(Action[] record, Action preAction, Action nowAction, Stack<Integer> fStack,
			Stack<Integer> tStack, String from, String to) {

		// 如果上一步动作为当前动作的相反动作（如上一步为L->M，则当前走M->L是无意义的）
		// 如果要移入的元素大于目标栈的栈顶元素是不合规则的（小压大）
		if (record[0] == preAction || fStack.peek() > tStack.peek()) {
			return 0;
		}

		tStack.push(fStack.pop());
		System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
		record[0] = nowAction;
		return 1;
	}
}
